package com.mlh.dp.old;

//给你一个下标从 0 开始的二维整数数组 questions ，其中 questions[i] = [pointsi, brainpoweri] 。
//这个数组表示一场考试里的一系列题目，你需要 按顺序 （也就是从问题 0 开始依次解决），
//针对每个问题选择 解决 或者 跳过 操作。解决问题 i 将让你 获得  pointsi 的分数，但是你将 无法 解决接下来的 brainpoweri 个问题（即只能跳过接下来的 brainpoweri 个问题）。
//如果你跳过问题 i ，你可以对下一个问题决定使用哪种操作。
//请你返回这场考试里你能获得的 最高 分数。

//输入：questions = [[1,1],[2,2],[3,3],[4,4],[5,5]]
//输出：7
//解释：解决问题 1 和 4 得到最高分。
//- 跳过问题 0
//- 解决问题 1 ：获得 2 分，但接下来 2 个问题都不能解决。
//- 不能解决问题 2 和 3
//- 解决问题 4 ：获得 5 分
//总得分为：2 + 5 = 7 。没有别的办法获得 7 分或者多于 7 分。

//此题注意数据类型啊  要用long  要不然结果会溢出
public class MostPoints {
	public static void main(String[] args) {
		int[][]questions={{3,2},{4,3},{4,4},{2,5}};
		System.out.println(method2(questions));
	}

	public static int method1(int[][] questions){
		return process1(questions,0);
	}

	public static int process1(int[][] questions,int index){
		if(index>=questions.length){
			return 0;
		}
		return  Math.max(process1(questions,index+questions[index][1]+1)+questions[index][0],process1(questions,index+1));
	}

	public static int method2(int[][] questions){
		int[]dp=new int[questions.length];
		return process2(questions,0,dp);
	}

	public static int process2(int[][] questions,int index,int[]dp){
		if(index>=questions.length){
			return 0;
		}
		if(dp[index]!=0){
			return dp[index];
		}
		dp[index]=Math.max(process1(questions,index+questions[index][1]+1)+questions[index][0],process1(questions,index+1));
		return dp[index];
	}

	public static long method3(int[][] questions){
		int n=questions.length-1;
		long []dp=new long [questions.length];
		dp[n]=questions[n][0];
		for(int i=n-1;i>=0;i--){
			if(i+questions[i][1]+1>n){
				dp[i]= Math.max(questions[i][0],dp[i+1]);
			}else{
				dp[i]= Math.max(dp[i+questions[i][1]+1]+questions[i][0],dp[i+1]);
			}
		}
		return dp[0];
	}

}
